# 102. 青蛙跳杯子(好题, BFS)
# https://www.lanqiao.cn/problems/102/learning/?page=1&first_category_id=1&second_category_id=3&contain_answer=true
# Date: 2025/2/4
from collections import deque


def jumping_frog(start: str, target: str):
    queue = deque([(start, start.index('*'), 0)])  # (当前状态, 空位索引, 步数)
    visited = set()  # 记录访问过的状态
    visited.add(start)

    while queue:
        state, empty_idx, steps = queue.popleft()

        # 如果当前状态是目标状态，则返回步数
        if state == target:
            return steps

        # 生成所有可能的跳跃
        for jump in [1, 2, 3]:  # 尝试跳1、2、3格
            for direction in [-1, 1]:  # 左跳 or 右跳
                new_idx = empty_idx + jump * direction
                if 0 <= new_idx < len(state):  # 确保跳跃不越界
                    # 交换位置
                    new_state = list(state)
                    new_state[empty_idx], new_state[new_idx] = new_state[new_idx], new_state[empty_idx]
                    new_state = ''.join(new_state)  # 将数组转换为字符串

                    # 如果该状态未访问过，则加入队列
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append((new_state, new_idx, steps + 1))

    return -1  # 如果无法达到目标状态


if __name__ == '__main__':
    # start = input()
    # target = input()
    print(jumping_frog("*WWBB", "WWBB*"))
    print(jumping_frog("*WWWBBB", "WWW*BBB"))
